package com.demo.java.OD501_550.OD531;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【最佳植树距离(E卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146496184
 */
public class OdMain {
    // 快速排序算法，用于对位置数组进行排序
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = arr[high]; // 选择基准元素
            int i = low - 1;
            for (int j = low; j < high; j++) {
                if (arr[j] <= pivot) { // 如果当前元素小于等于基准元素
                    i++;
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
            int temp = arr[i + 1];
            arr[i + 1] = arr[high];
            arr[high] = temp;

            int partitionIndex = i + 1;
            quickSort(arr, low, partitionIndex - 1); // 对左边部分递归排序
            quickSort(arr, partitionIndex + 1, high); // 对右边部分递归排序
        }
    }

    // 检查在给定的最小间距下，是否能够种下所需数量的树
    public static boolean canPlant(int[] positions, int n, int trees, int distance) {
        int count = 1; // 第一棵树必定种在第一个位置
        int lastPosition = positions[0]; // 记录最后一棵树的位置
        for (int i = 1; i < n; i++) {
            // 如果当前树和上一棵树的间距大于等于指定的最小间距
            if (positions[i] - lastPosition >= distance) {
                count++; // 放置一棵树
                lastPosition = positions[i]; // 更新最后一棵树的位置
                if (count >= trees) return true; // 如果已经种下所需的树木数量
            }
        }
        return false; // 无法种下足够的树木
    }

    // 使用二分查找法来找出最大最小间距
    public static int findMaxDistance(int[] positions, int n, int trees) {
        int left = 1; // 最小间距为1
        int right = positions[n - 1] - positions[0]; // 最大间距为最大坐标值与最小坐标值之差
        int result = 0;

        while (left <= right) {
            int mid = (left + right) / 2; // 计算中间的间距
            if (canPlant(positions, n, trees, mid)) {
                result = mid; // 如果能种下所需数量的树木，更新结果
                left = mid + 1; // 增大最小间距
            } else {
                right = mid - 1; // 减小最小间距
            }
        }
        return result; // 返回最大最小间距
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 树的位置数量
        int[] positions = new int[n];
        for (int i = 0; i < n; ++i) {
            positions[i] = in.nextInt(); // 读取每个位置
        }
        int trees = in.nextInt(); // 需要种植的树的数量

        quickSort(positions, 0, n - 1); // 排序
        int maxDistance = findMaxDistance(positions, n, trees); // 查找最大最小间距
        System.out.println(maxDistance); // 输出结果
    }
}